\chapter{Overview of Wireless Sensor Networks and Localization}
\section{Wireless Sensor Networks}

A wireless sensor network (WSN) consists of a set of nodes tasked with sensing environmental phenomenon at or near each node.  Nodes communicate via radios to send their data back to a central acquisition system.  Nodes are typically small, cheap devices and are designed with power efficiency in mind to prolong the lifetime of the network's ability to collect data.  Nodes are often distributed in the field of interest randomly, sometimes even by dropping them from the air, as on a military battlefield.  Other times, they are placed in specific, but unknown a priori, locations, as in placing them in bird nests\cite{birds}.  Or, they may be rolled into a transportation tunnel to give firefighters and emergency crews current information about heat and oxygen levels \cite{runes}.

A number of issues arise when designing a WSN.  Each node must be able to communicate with  other nodes and send data to a central collection site.  Each node must know what time it is, for purposes of data sampling, and often for routing protocols as well.  Further, each node must know where it is so spatial data can be properly correlated.  Location can also be useful for geographic routing protocols.  This thesis focuses on determining the location of each node as accurately as possible.

\section{Localization Protocols}

There are two general classes of localization protocols: ranging and range-free. Ranging protocols rely on information from the radio. With this information, a fairly accurate network topology can be built.  Ranging techniques can use a variety of metrics to build the network topology.  These include Time-of-Arrival (TOA), like GPS\cite{Wellenhoff},  Time-Differential-of-Arrival (TDOA)\cite{Savvides}, Angle-of-Arrival (AOA)\cite{APS-AOA}, or Received-Signal-Strength-Indicator (RSSI)\cite{Patwari}.  

However, the special hardware and power requirement to perform these ranging techniques is counter to the goal of low-cost, low-power nodes, and thus we exclude ranging protocols from our study.  Regardless, if a ranging protocol does build a relative map, and then does a post-processing step by mapping this relative map to a global map based on a subset of anchor nodes, the results of this thesis apply to ranging as well as range-free protocols.

Range-free protocols do not rely on any specialized hardware for additional information.  Rather, they rely solely on network connectivity, specifically knowledge of their direct neighbors.  Often, a node will collect information about their direct neighbors' neighbors as well, known as two-hop information.  Knowledge of each further node requires more information to be shared and therefore transmitted between nodes, thus requiring more power for radio transmission.  It is for this reason that only one-hop or possibly two-hop knowledge is preferred.

\subsection{Ad Hoc Positioning System}
Niculesu, et al. propose a distributed localization algorithm known as Ad Hoc Positioning System (APS)\cite{APS}.  It is similar to GPS in that is uses triangulation to determine node positions.  In APS, each node maintains a table of distances to each anchor.  The distance can be represented as a hop count, estimated distance using RSSI, or Euclidean distance.  As a distributed algorithm, each node determines its own position based on the distances to the anchor nodes.  Thus, APS does not perform well in anisotropic network, that is networks with holes or "C" shapes in the topology, because the communication distance can be far greater than the geometric distance between two nodes.

In its simplest form, APS uses a propagation technique called DV-HOP to determine distances between nodes.  DV-HOP is based on classical distance vector exchange from general network protocols like TCP/IP.  Each node maintains a table of hop counts between all known nodes.  Each node exchanges this table only with its direct neighbors.  When an anchor has discovered a hop count to another anchor, the anchor estimates the average distance for each hop since it knows the absolute location of itself and the other anchor. 
This correction factor is sent to the entire network.  DV-HOP thus minimizes the amount of data that must be transmitted in the network.  

Further, APS can employ a propagation technique called DV-distance.  DV-distance is similar to DV-hop except that it uses RSSI to determine each hop distance and sends this distance instead of hop count.  This difference allows DV-distance to effectively detect holes and curves in the network as each anchor can see that the transmission path between them is larger than the Euclidean distance.

\subsection{MDS-MAP}
Shang, et al. attempt to correct the errors introduced by APS and other distributed algorithms through a centralized localization algorithm called MDS-MAP(C)\cite{MDS-MAP}, where the \emph{C} is for centralized.  MDS-MAP(C) is divided into three phases.  In phase one, shortest path distances or hop counts are exchanged via a distance vector exchange, similar to APS.  This provides a rough estimate of the distance between each pair of sensors.  In phase two, multi-dimensional scaling (MDS) is applied, resulting in a relative map.  MDS is a general data analysis tool originating from psychophysics\cite[p.2]{MDS-MAP} to transform data from many to few dimensions.  In simple terms, MDS takes a set of distances between points and creates a structure that fits those distances.  Often, it is used for general data visualization.  In this case, the relative map conforms closely to the pair-wise distances provided.  In phase three of MDS-MAP(C), the relative map is transformed into a global coordinate system using at least three anchors using the Procrustes algorithm.  Procrustes is described in more detail in Section~\ref{sec:procrustes}.

The authors provided a modified, distributed version, MDS-MAP(P)\cite{MDS-MAP-P}.  This variation simply divides the network into smaller, more manageable sections so that the algorithm can be performed locally, with the limited node resources available.  Each local map is then patched together, and hence the \emph{P} for patched.  The patching part of the algorithm is not distributed.  Local map merging begins at a randomly selected node's local map, and chooses the local map with the most overlapping nodes.  The process continues until all the local maps are merged together.  

\subsection{CCA-MAP} \label{sec:CCA-MAP}
Li, et al, propose a similar style algorithm to MDS-MAP called CCA-MAP\cite{CCA-MAP07,CCA-MAP09}.  It is similar in that it generates relative, local maps of sections of the network and then patches them together into a global coordinate system.  CCA-MAP improves on MDS-MAP in that the algorithm is more efficient.  MDS is a non-linear reduction algorithm and has a computational cost of \emph{O($n^{3}$)}, where \emph{n} is the number of nodes in each local map.  The size of each local map is dependent on the radio range which affects the number of neighbors for each sensor node.  Further, the algorithm could be run in a centralized way, which means that \emph{n} becomes the total number of nodes in the network. CCA\cite{CCA} on the other hand, is a self-organized neural network performing quantization and non-linear projection.  CCA-MAP has a total computational cost of \emph{O($n^{2}$)}.  CCA runs in a series of iterations, where each iteration has a computational cost of \emph{O(n)}.

CCA-MAP has four phases.  In the first phase, each node builds a local map of nodes within \emph{R} hops.  For that local map, the shortest distance matrix is accumulated, as in APS and MDS-MAP.  The second phase involves performing the CCA algorithm itself on each local map, generating relative coordinates for each node in the local map.  In phase three, the local maps are merged together, as in MDS-MAP(P), and finally, in phase four, the relative coordinates are transformed into absolute coordinates based on the known coordinates of the anchor nodes, as described in Section~\ref{sec:procrustes}.  Phase four can only be performed with a minimum of three anchors for \emph{2D} space or four anchors for \emph{3D} space.  

CCA-MAP is flexible as to where computations can be performed. Local map calculations can be performed at the nodes themselves, if computing resources allow, or outsourced to more powerful gateway nodes or a central server.  Local map merging can be performed in parallel at selected nodes in the network, or again at a central server.  Further, if in any sub-map sufficient anchors are found, then absolute coordinates can be calculated.

